package com.leetcode.动态规划.买卖股票的最佳时机;

public class L188买卖股票的最佳时机IV {
	public static void main(String[] args) {
		int result = maxProfit(2,new int[] {3,2,6,5,0,3});
		System.out.println(result);
	}

	public static int maxProfit(int k,int[] prices) {
		/**
		 * 根据L123买卖股票的最佳时机III的规律，分别设：第n次买入和第n次卖出的状态
		 * dp[i][0]:表示第i天无操作
		 * dp[i][j]:表示第(j + 1) / 2 次买入所得的最大现金
		 * 有两种状态得来：1、dp[i - 1][j]：第i天之前就已经买入
		 * 			   2、dp[i - 1][j - 1] - prices[i]:第i天买入
		 * dp[i][j + 1]:表示第(j + 1) / 2 次卖出所得的最大现金
		 * 有两种状态得来：1、dp[i - 1][j + 1]：第i天之前就已经卖出
		 * 			   2、dp[i - 1][j] + prices[i]:第i天卖出
		 */
		if(prices.length == 0) return 0;
		int len = prices.length;
		int[][] dp = new int[len][2 * k + 1];
		for(int j = 1;j < 2 * k;j += 2) {
			dp[0][j] = -prices[0];
		}
		for(int i = 1;i < len;i++) {
			dp[i][0] = dp[i - 1][0];
			for(int j = 1;j < 2 * k;j += 2) {
				dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - 1] - prices[i]);
				dp[i][j + 1] = Math.max(dp[i - 1][j + 1],dp[i - 1][j] + prices[i]);
			}
		}
		return dp[len - 1][2 * k];
	}
}
